Suma cyfr 2

Limit pamięci: 64 MB

Dana jest pewna bardzo długa liczba. Możemy dowolnie zwiększyć niektóre cyfry tej liczby, jednak nie możemy zwiększyć żadnych dwóch sąsiednich cyfr. Chcemy, aby powstała w ten sposób liczba miała jak największą sumę cyfr.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę cyfr zadanej liczby. W drugim wierszu znajduje się ciąg cyfr liczby, pooddzielany dla wygody pojedynczymi odstępami.

W testach wartych 50% punktów zachodzi dodatkowy warunek .

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać jedną liczbę całkowitą: maksymalną sumę cyfr liczby, jaką da się osiągnąć w podany sposób.

Przykład

Dla danych wejściowych:

4
5 7 8 5

poprawną odpowiedzią jest:

33

Wyjaśnienie do przykładu: Spośród liczb możliwych do osiągnięcia maksymalną sumę cyfr ma 9789.